{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Time Needed to Rearrange a Binary String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: secondsToRemoveOccurrences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二进制字符串重新安排顺序需要的时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串&nbsp;<code>s</code>&nbsp;。在一秒之中，<strong>所有</strong>&nbsp;子字符串&nbsp;<code>\"01\"</code> <strong>同时</strong>&nbsp;被替换成&nbsp;<code>\"10\"</code>&nbsp;。这个过程持续进行到没有&nbsp;<code>\"01\"</code>&nbsp;存在。</p>\n",
    "\n",
    "<p>请你返回完成这个过程所需要的秒数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"0110101\"\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>\n",
    "一秒后，s 变成 \"1011010\" 。\n",
    "再过 1 秒后，s 变成 \"1101100\" 。\n",
    "第三秒过后，s 变成 \"1110100\" 。\n",
    "第四秒后，s 变成 \"1111000\" 。\n",
    "此时没有 \"01\" 存在，整个过程花费 4 秒。\n",
    "所以我们返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"11100\"\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "s 中没有 \"01\" 存在，整个过程花费 0 秒。\n",
    "所以我们返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s[i]</code>&nbsp;要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<p>你能以 O(n) 的时间复杂度解决这个问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [time-needed-to-rearrange-a-binary-string](https://leetcode.cn/problems/time-needed-to-rearrange-a-binary-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [time-needed-to-rearrange-a-binary-string](https://leetcode.cn/problems/time-needed-to-rearrange-a-binary-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"0110101\"', '\"11100\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        # res=0\n",
    "        # while '01' in s:\n",
    "        #     s=s.replace('01','10')\n",
    "        #     res+=1\n",
    "        # return res\n",
    "        n=len(s)\n",
    "        dp=pre=0\n",
    "        for i in s:\n",
    "            if i=='0':\n",
    "                pre+=1\n",
    "            elif pre:\n",
    "                dp=max(dp+1,pre)\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        l, r = 0, len(s) - 1\n",
    "        while l < len(s) and s[l] != '0':\n",
    "            l += 1\n",
    "        while r >= 0 and s[r] != '1':\n",
    "            r -= 1\n",
    "\n",
    "        c0, c1 = 0, 0\n",
    "        for i in range(l, r):\n",
    "            if s[i] == '0':\n",
    "                c0 += 1\n",
    "                c1 = max(0, c1 - 1)\n",
    "            else:\n",
    "                if c0 > 0:\n",
    "                    c1 += 1\n",
    "            \n",
    "        return c0 + c1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        f = pre0 = 0\n",
    "        for c in s:\n",
    "            if c == '0': pre0 += 1\n",
    "            elif pre0: f = max(f + 1, pre0)  # 前面有 0 的时候才会移动\n",
    "        return f\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        # DP\n",
    "        f = pre0 = 0\n",
    "        for c in s:\n",
    "            if c == '0': pre0 += 1\n",
    "            elif pre0: f = max(f + 1, pre0)  # 前面有 0 的时候才会移动\n",
    "        return f\n",
    "\n",
    "        # 暴力\n",
    "        res = 0\n",
    "        while '01' in s:\n",
    "            s = s.replace('01','10')\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        #x 个泡泡  \n",
    "        f = pre0 = 0\n",
    "        for c in s:\n",
    "            if c == '0': pre0 += 1\n",
    "            elif pre0: f = max(f+1, pre0)\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        f = pre0 = 0\n",
    "        for c in s:\n",
    "            if c == '0': pre0 += 1\n",
    "            elif pre0: f = max(f + 1, pre0)  # 前面有 0 的时候才会移动\n",
    "        return f\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        result = 0\n",
    "        while '01' in s :\n",
    "            s = s.replace('01','10')\n",
    "            result += 1\n",
    "            pass\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        while '01' in s:\n",
    "            ans += 1\n",
    "            s = s.replace('01', '10')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        while \"01\" in s:\n",
    "            s = s.replace(\"01\", \"10\")\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "\n",
    "\n",
    "        res, cnt = 0, 0\n",
    "\n",
    "        for c in s:\n",
    "\n",
    "            if c == \"0\": cnt += 1\n",
    "            elif cnt: res = max(res + 1, cnt)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        res=0\n",
    "        cnt=0\n",
    "        for c in s:\n",
    "            if c=='0':\n",
    "                cnt+=1\n",
    "            elif cnt:\n",
    "                res=max(res+1,cnt)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        count = 0\n",
    "        \n",
    "        while True:\n",
    "            \n",
    "            if \"01\" in s:\n",
    "                s = s.replace(\"01\", \"10\")\n",
    "                count += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        f = pre = 0\n",
    "        for c in s:\n",
    "            if c == '0': pre += 1\n",
    "            elif pre: f = max(f + 1, pre)\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        pre_zero = f = 0\n",
    "        for ch in s:\n",
    "            if ch == '0':\n",
    "                pre_zero += 1\n",
    "            elif pre_zero:\n",
    "                f = max(f+1, pre_zero)\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "      #last=\"\"\n",
    "      c=0\n",
    "      while True:\n",
    "        last,s=s,s.replace(\"01\",\"10\")\n",
    "        if s==last:\n",
    "          break\n",
    "        c+=1\n",
    "      return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        f=pre0=0\n",
    "        for c in s:\n",
    "            if c == '0':\n",
    "                pre0+=1\n",
    "            elif pre0:\n",
    "                f = max(f+1,pre0)\n",
    "        return f      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        res, cnt = 0, 0\n",
    "\n",
    "        for c in s:\n",
    "\n",
    "            if c == '0': cnt += 1\n",
    "\n",
    "            elif cnt: res = max(res + 1, cnt)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        f1 = f2 = 0\n",
    "        for c in s:\n",
    "            if c == '0':\n",
    "                f1 += 1\n",
    "            elif f1:\n",
    "                f2 = max(f2 + 1, f1)\n",
    "        return f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        # 暴力模拟\n",
    "        ans = 0\n",
    "        while '01' in s:\n",
    "            s = s.replace('01', '10')\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        while '01' in s:\n",
    "            s = s.replace('01', '10')\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        res, cnt = 0, 0\n",
    "        for c in s:\n",
    "            if c == '0': cnt += 1\n",
    "            elif cnt: res = max(res + 1, cnt)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        result = 0\n",
    "        zeros = 0\n",
    "        for c in s:\n",
    "            if(c == '0'):\n",
    "                zeros += 1\n",
    "            else:\n",
    "                if(zeros > 0):\n",
    "                    result = max(result + 1, zeros)\n",
    "\n",
    "        return result\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        while True:\n",
    "            tmp = s \n",
    "            s = s.replace('01', '10')\n",
    "            if tmp == s:\n",
    "                return ans\n",
    "            ans += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        res, cnt = 0, 0\n",
    "        for c in s:\n",
    "            if c == '0': cnt += 1\n",
    "            elif cnt: res = max(res + 1, cnt)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        n1=s.count(\"1\")\n",
    "        target=[1]*n1+[0]*(n-n1)\n",
    "        lst=[]\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            lst.append(int(s[i]))\n",
    "        while target!=lst:\n",
    "            id0=0\n",
    "            while id0<n-1:\n",
    "                if lst[id0]==0 and lst[id0+1]==1:\n",
    "                    lst[id0]=1\n",
    "                    lst[id0+1]=0\n",
    "                    id0+=2\n",
    "                else:\n",
    "                    id0+=1\n",
    "            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        ans = 0\n",
    "        flag = False\n",
    "        while not flag:\n",
    "            flag = True\n",
    "            i = 0\n",
    "            while i < n-1:\n",
    "                if s[i] == '0' and s[i + 1] == '1':\n",
    "                    s[i], s[i + 1] = s[i + 1], s[i]\n",
    "                    flag = False\n",
    "                    i += 1\n",
    "                i += 1\n",
    "            ans += 1\n",
    "\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        f = pre0 = 0\n",
    "        for c in s:\n",
    "            if c == '0': pre0 += 1\n",
    "            elif pre0: f = max(f + 1, pre0)  # 前面有 0 的时候才会移动\n",
    "        return f\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        f=pre0=0\n",
    "        for c in s:\n",
    "            if c=='0':pre0+=1\n",
    "            elif pre0:f=max(f+1,pre0)\n",
    "        return f    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        # pre_zero = f = 0\n",
    "        # for ch in s:\n",
    "        #     if ch == '0':\n",
    "        #         pre_zero += 1\n",
    "        #     elif pre_zero:\n",
    "        #         f = max(f+1, pre_zero)\n",
    "        # return f\n",
    "\n",
    "        # ------------------------------\n",
    "        res = 0\n",
    "        while '01' in s:\n",
    "            s = s.replace('01', '10')\n",
    "            res += 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        while \"01\" in s:\n",
    "            s = s.replace(\"01\", \"10\")\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        lastLen = zeros = endDelay = result = 0\n",
    "        for v, grp in groupby(s):\n",
    "            _len = sum(1 for _ in grp)\n",
    "            if v == '0':\n",
    "                zeros += _len\n",
    "            elif zeros:\n",
    "                startDelay = max(endDelay+1, lastLen) - lastLen\n",
    "                endDelay = startDelay + _len - 1\n",
    "                result = endDelay + zeros\n",
    "            lastLen = _len\n",
    "        return result \n",
    "        # 001011101\n",
    "        # 010101110\n",
    "        # 1010101\n",
    "        # 1101010\n",
    "        # 1110100\n",
    "        # 1111000\n",
    "        # 00011101\n",
    "        # 00101110\n",
    "        # 01010110\n",
    "        # 10101010\n",
    "\n",
    "        # lastLen\n",
    "        # 110101\n",
    "        # 111010"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        # 暴力\n",
    "        res = 0\n",
    "        while '01' in s:\n",
    "            s = s.replace('01','10')\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        steps = 0\n",
    "        zero_cnt = 0\n",
    "\n",
    "        for item in s:\n",
    "            if item == '0':\n",
    "                zero_cnt += 1\n",
    "            elif zero_cnt:\n",
    "                steps = max(zero_cnt, steps + 1)\n",
    "        \n",
    "        return steps\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        i = 0 \n",
    "        while '01' in s:\n",
    "            s = s.replace('01', '10')\n",
    "            i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        res, cnt = 0, 0\n",
    "        for c in s:\n",
    "            if c == '0': cnt += 1\n",
    "            elif cnt: res = max(res + 1, cnt)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        res,cnt=0,0\n",
    "        for c in s:\n",
    "            if c=='0': cnt+=1\n",
    "            elif cnt: res=max(res+1,cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        res,cnt=0,0\n",
    "        for c in s:\n",
    "            if c=='0':\n",
    "                cnt+=1\n",
    "            elif cnt:\n",
    "                res=max(res+1,cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        while \"01\" in s:\n",
    "            cnt += 1\n",
    "            s = s.replace(\"01\",\"10\")\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        a = 0\n",
    "\n",
    "        while ('01' in s):\n",
    "            s=s.replace('01','10')\n",
    "            a+=1\n",
    "        return a\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def secondsToRemoveOccurrences(self, s: str) -> int:\n",
    "        res, cnt = 0, 0\n",
    "        for c in s:\n",
    "            if c == '0':\n",
    "                 cnt += 1\n",
    "            elif cnt:\n",
    "                 res = max(res + 1, cnt)\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
